class Solution {
public:
    int lowerBound(int A[], int n, int target) {
        int low = 0;
        int high = n;
        int mid = 0;

        while (low < high) {
            mid = low + (high - low) / 2;
            if (A[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    int upperBound(int A[], int n, int target) {
        int low = 0;
        int high = n;
        int mid = 0;

        while (low < high) {
            mid = low + (high - low) / 2;
            if (A[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int start = lowerBound(A, n, target);
        int end = upperBound(A, n, target);
        vector<int> ans;

        if (start == end) {
            ans.push_back(-1);
            ans.push_back(-1);
        } else {
            ans.push_back(start);
            ans.push_back(end - 1);
        }
        return ans;
    }
};
